package BinaryTree;

/**
 * 获取一颗二叉树的子树中，节点最多的搜索二叉树的头节点
 *
 * 使用递归套路，时间复杂度O（n)
 *
 * @author Liaorun
 */
public class BiggestSubBSTinTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class ReturnData {
        public int maxBSTSize;
        public boolean isAllBST;
        public int max;
        public int min;

        public ReturnData(int maxBSTSize, boolean isAllBST, int max, int min) {
            this.maxBSTSize = maxBSTSize;
            this.isAllBST = isAllBST;
            this.max = max;
            this.min = min;
        }
    }

    public static class Info {
        public Node maxBSTHead;
        /**
         * 是否是搜索二叉树
         */
        public boolean isBST;
        /**
         * 树上的最小值
         */
        public int min;
        /**
         * 树上的最大值
         */
        public int max;
        /**
         * 节点数量
         */
        public int maxBSTSize;

        public Info(Node maxBSTHead, boolean isBST, int min, int max, int maxBSTSize) {
            this.maxBSTHead = maxBSTHead;
            this.isBST = isBST;
            this.min = min;
            this.max = max;
            this.maxBSTSize = maxBSTSize;
        }
    }

    public static Info process(Node x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int min = x.value;
        int max = x.value;
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }

        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }

        // 下面探讨可能性1，2，3
        int maxBSTSize = 0;
        Node maxBSTHead = null;

        if (leftInfo != null) {
            maxBSTSize = leftInfo.maxBSTSize;
            maxBSTHead = leftInfo.maxBSTHead;
        }

        // 有右子树 && 有右子树的节点个数更大
        if (rightInfo != null && rightInfo.maxBSTSize > maxBSTSize) {
            maxBSTSize = rightInfo.maxBSTSize;
            maxBSTHead = rightInfo.maxBSTHead;
        }
        boolean isBST = false;

        // 判断左子树 和 右子树是不是搜索二叉树
        if ((leftInfo == null || leftInfo.isBST) && (rightInfo == null || rightInfo.isBST)) {

            // 判断左子树和右子树和当前节点一起的树，是不是搜索二叉树
            // 左树的最大值 < 当前节点值 &&  右树的最小值 > 当前节点值
            if ((leftInfo == null || leftInfo.max < x.value) && (rightInfo == null || rightInfo.min > x.value)) {
                isBST = true;
                maxBSTHead = x;
                maxBSTSize = (leftInfo == null ? 0 : leftInfo.maxBSTSize) + (rightInfo == null ? 0 : rightInfo.maxBSTSize) + 1;
            }
        }


        return new Info(maxBSTHead, isBST, min, max, maxBSTSize);
    }
}
